|
In mathematics and computer science, Zeno machines (abbreviated ZM, and also called accelerated Turing machine, ATM) are a hypothetical computational model related to Turing machines that allows a countably infinite number of algorithmic steps to be performed in finite time. These machines are ruled out in most models of computation. More formally, a Zeno machine is a Turing machine that takes 2−''n'' units of time to perform its ''n''-th step; thus, the first step takes 0.5 units of time, the second takes 0.25, the third 0.125 and so on, so that after one unit of time, a countably infinite (i.e. ℵ0) number of steps will have been performed. The idea of Zeno machines was first discussed by Hermann Weyl in 1927; the name refers to Zeno's paradoxes, attributed to the ancient Greek philosopher Zeno of Elea. Zeno machines play a crucial role in some theories. The theory of the Omega Point devised by physicist Frank J. Tipler, for instance, can only be valid if Zeno machines are possible. == Zeno machines and computability == Zeno machines allow some functions to be computed that are not Turing-computable. For example, the halting problem for Turing machines can easily be solved by a Zeno machine (using the following pseudocode algorithm): begin program write 0 on the first position of the output tape; begin loop simulate 1 successive step of the given Turing machine on the given input; if the Turing machine has halted, then write 1 on the first position of the output tape and break out of loop; end loop end program Computing of this kind that goes beyond the Turing Limit is called hypercomputation. It is also an example of a supertask. Also, the halting problem for Zeno machines is not solvable by a Zeno machine (Potgieter, 2006). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zeno machine」の詳細全文を読む スポンサード リンク
|